open Uav_data
open Target
open Planning

module P = struct
  let t0 = Sys.time ()

  let init = fun () ->
    let res = {ball = Array.copy ball; video = Array.copy video } in
    let tasks = generate_random_alloc res in
    let plans = Insertion.generate_plans tasks in
    { tasks = tasks; res = res; plans = plans;}

  let shaking = fun planning  (i: int) ->
    let planning = planning_copy planning in
    let task_pool = Array.to_list (Array.init n (fun i -> i)) in
    let choose_in_pool = fun pool k ->
      let rec choose = fun pool k chosen ->
	if k <= 0 then chosen
	else
	  begin
	    let idx = Random.int (List.length pool) in
	    let c = List.nth pool idx in
	    choose (List.filter (fun x-> x<>c) pool) (k-1) (c::chosen)
	  end in
      choose pool k [] in
    let remove_pool = choose_in_pool task_pool (min n (3+(Random.int 4))) in
     List.iter (fun i -> remove_task_from_plan i planning ) remove_pool;
    (remove_pool, planning)

  let local_search = fun (pool, planning) ->
    let nbrhd = ref [] in
    let rec search = fun pool planning ->
      match pool with
	  [] -> 
	    nbrhd := planning :: !nbrhd
	| t::pool ->
	    let machines = available_machine_for_task t planning.res in
	    List.iter 
	      (fun machine ->
		 let planning = planning_copy planning in
		 if ttype.(t) = Dr 
		 then planning.res.ball.(machine) 
		   <- planning.res.ball.(machine) -1;
		 planning.tasks.(t) <- machine;
		 planning.plans.(machine) <- 
		   Insertion.insert_at_best_position 
		   t planning.plans.(machine) machine;
		 search pool planning
	      ) machines;
    in
    search pool planning;
    !nbrhd

  type eval_t = int array

  let cost = fun planning ->
    Array.mapi (fun k _ -> plan_cost planning.plans k) planning.plans

  exception Leximin_false
  exception Leximin_true

  let cmp = fun e1 e2 ->
    let e1 = Array.copy e1 in
    let e2 = Array.copy e2 in
    Array.sort (fun a b -> - compare a b) e1;
    Array.sort (fun a b -> - compare a b) e2;
    try 
      for i=0 to Array.length e1 -1 do
	if e1.(i) < e2.(i) then raise Leximin_true;
	if e2.(i) < e1.(i) then raise Leximin_false;
      done;
      false
    with
	Leximin_true -> true
      | Leximin_false -> false

  let print = fun planning -> 
    Printf.printf "%04.2f\t" (Sys.time () -. t0);
    let c =  Array.mapi 
      (fun k _ -> plan_cost planning.plans k) planning.plans in
    Printf.printf "%d\t\t" (Utils.max_array c);
    Array.iter (fun c -> Printf.printf "%d\t" c) c;
    print_newline();
    trace planning.plans
    
end

module S = Lns.Make(P)

let _ = 
  S.start ttype ball video time

